﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;


namespace Ysz
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
        {
            _val = val;
        }
        ListNode<T>* _pPre = nullptr;
        ListNode<T>* _pNext = nullptr;
        T _val;
    };


    //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
        ListIterator(PNode pNode = nullptr)
        {
            _pNode = pNode;
        }
        ListIterator(const Self& l)
        {
            _pNode = l._pNode;
        }
        Ref operator*()
        {
            return _pNode->_val;
        }
        Ptr operator->()
        {
            return &_pNode->_val;
        }
        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }
        Self operator++(int)
        {
            Self node = _pNode;
            _pNode = _pNode->_pNext;
            return node;
        }
        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;

        }
        Self operator--(int)
        {
            Self node = _pNode;
            _pNode = _pNode->_pPre;
            return node;
        }
        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }
        bool operator==(const Self& l)
        {
            return _pNode == l._pNode;

        }
        PNode _pNode;
    };


    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T&> const_iterator;
    public:
        ///////////////////////////////////////////////////////////////
        // List的构造
        


        list()
        {
            CreateHead();
        }
        list(int n, const T& value = T())
        {
            CreateHead();
            for (size_t i = 0; i < n; i++)
            {
                push_back(value);
            }
        }
        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }
        list(const list<T>& l)
        {
            CreateHead();

            for (auto& x : l)
            {
                push_back(x);
            }
        }
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }
        ~list()
        {
            
            if(_size != 0)
            {
                iterator it = begin();
                iterator cur = begin();
                while (it != end())
                {
                    cur = it++;
                    delete cur._pNode;
                }
            }
            delete _pHead;
        }


        ///////////////////////////////////////////////////////////////
        // List Iterator
        iterator begin()
        {
            return _pHead->_pNext;
        }
        iterator end()
        {
            return _pHead;
        }
        const_iterator begin() const
        {
            return _pHead->_pNext;

        }
        const_iterator end() const
        {
            return _pHead;

        }


        ///////////////////////////////////////////////////////////////
        // List Capacity
        size_t size()const
        {
            return _size;
        }
        bool empty()const
        {
            return _size == 0;
        }


        ////////////////////////////////////////////////////////////
        // List Access
        T& front()
        {
            //it begin()
            iterator it = begin();
            return it._pNode->_val;
        }
        const T& front()const
        {
            const_iterator it = begin();
            return it._pNode->_val;
        }
        T& back()
        {
            iterator it = _pHead->_pPre;
            return it._pNode->_val;
        }
        const T& back()const
        {
            const_iterator it = _pHead->_pPre;
            return it._pNode->_val;
        }


        ////////////////////////////////////////////////////////////
        // List Modify
        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) { insert(begin(), val); }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            PNode tmp = new Node(val);
            PNode cur = pos._pNode;
            PNode prv = cur->_pPre;
            tmp->_pNext = cur;
            tmp->_pPre = prv;
            prv->_pNext = tmp;
            cur->_pPre = tmp;
            _size++;
            return tmp;
        }
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            assert(pos != end());
            PNode pre = pos._pNode->_pPre;
            PNode pnext = pos._pNode->_pNext;
            pre->_pNext = pnext;
            pnext->_pPre = pre;
            delete(pos._pNode);
            _size--;
            return pnext;
        }
            

        
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                it = erase(it);
            }
        }
        void swap(list<T>& l)
        {
            std::swap(_pHead, l._pHead);
            std::swap(_size, l._size);

        }
    private:
        size_t _size = 0;
        void CreateHead()
        {
            
           PNode tmp = new Node();
           tmp->_pNext = tmp;
           tmp->_pPre = tmp;
           _pHead = tmp;
        }
        PNode _pHead;
    };
};
